package mo.leetcode_top;

import java.util.*;

public class L792 {

    //"dsahjpjauf"
    //["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]

    //"abcde"
    //["a","bb","acd","ace"]

    class Node {
        public String word;
        public int index;

        public Node() {
        }

        public Node(String word, int index) {
            this.word = word;
            this.index = index;
        }
    }

    public int numMatchingSubseq2(String s, String[] words) {
        List<Node>[] nodesByHead = new ArrayList[26];
        for (int i = 0; i < nodesByHead.length; i++) {
            nodesByHead[i] = new ArrayList<>();
        }
        for (String word : words) {
            nodesByHead[word.charAt(0)-'a'].add(new Node(word, 0));
        }
        int res = 0;
        for (char c : s.toCharArray()) {
            List<Node> old = nodesByHead[c-'a'];
            nodesByHead[c-'a'] = new ArrayList<>();
            for (Node node : old) {
                node.index++;
                if (node.index == node.word.length()) {
                    res++;
                } else {
                    nodesByHead[node.word.charAt(node.index)-'a'].add(node);
                }
            }
        }
        return res;
    }

    public int numMatchingSubseq(String s, String[] words) {

        boolean[] charSet = new boolean[26];
        for (char c : s.toCharArray()) {
            charSet[c-'a'] = true;
        }

        int i = 0;
        int len = s.length();
        int res = 0;
        for (String word : words) {
            i = 0;
            res++;
            char[] wordChar = word.toCharArray();
            for (char c : wordChar) {
                if (!charSet[c - 'a']) {
                    res--;
                    break;
                }
                while (i < len && s.charAt(i) != c) {
                    i++;
                }
                i++;
                if (i > len) {
                    res--;
                    break;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        L792 test = new L792();
        System.out.println(test.numMatchingSubseq2("dsahjpjauf", new String[]{"ahjpjau","ja","ahbwzgqnuk","tnmlanowax"}));
        System.out.println(test.numMatchingSubseq2("abcde", new String[]{"a","bb","acd","ace"}));
    }
}
